package ADD_project;
import java.util.Arrays;

public class ClosestPairProble {
    // 计算两个点之间的欧几里得距离
    private static double dist(Point p1, Point p2) {
        return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
    }

    // 暴力枚举求解最接近点对
    private static double bruteForce(Point[] points, int start, int end) {
        double minDist = Double.POSITIVE_INFINITY;
        for (int i = start; i <= end; i++) {
            for (int j = i + 1; j <= end; j++) {
                double d = dist(points[i], points[j]);
                if (d < minDist) {
                    minDist = d;
                }
            }
        }
        return minDist;
    }

    // 使用分治法求解最接近点对
    private static double closestPair(Point[] points, int start, int end) {
        int n = end - start + 1;

        if (n <= 3) {
            // 如果点的数量小于等于 3，直接使用暴力枚举求解
            return bruteForce(points, start, end);
        } else {
            // 将点集分成左右两部分，并递归求解左右两部分的最接近点对
            int mid = (start + end) / 2;
            double dLeft = closestPair(points, start, mid);
            double dRight = closestPair(points, mid + 1, end);

            // 合并结果
            double d = Math.min(dLeft, dRight);
            Point[] strip = new Point[n];
            int stripIndex = 0;
            for (int i = start; i <= end; i++) {
                if (Math.abs(points[i].x - points[mid].x) < d) {
                    strip[stripIndex++] = points[i];
                }
            }
            Arrays.sort(strip, 0, stripIndex, (p1, p2) -> Double.compare(p1.y, p2.y));

            // 在 strip 中计算最接近点对的距离
            double minStrip = Double.POSITIVE_INFINITY;
            for (int i = 0; i < stripIndex; i++) {
                for (int j = i + 1; j < stripIndex && strip[j].y - strip[i].y < d; j++) {
                    double dStrip = dist(strip[i], strip[j]);
                    if (dStrip < minStrip) {
                        minStrip = dStrip;
                    }
                }
            }
            return Math.min(d, minStrip);
        }
    }

    static class Point {
        double x;
        double y;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        Point[] points = {new Point(2, 3), new Point(12, 30), new Point(40, 50), new Point(5, 1), new Point(12, 10), new Point(3, 4)};
        Arrays.sort(points, (p1, p2) -> Double.compare(p1.x, p2.x));
        double minDist = closestPair(points, 0, points.length - 1);
        System.out.println(minDist); // 输出：2.8284271247461903
    }
}
